package problem115_Distinct_Subsequences;

public class Solution {
	public int numDistinct(String s, String t) {
		int[][] dp=new int[s.length()+1][t.length()+1];
		char[] sChars=s.toCharArray();
		char[] tChars=t.toCharArray();
		for(int i=0;i<=sChars.length;i++){
			dp[i][0]=1;
		}
		for(int i=1;i<=sChars.length;i++){
			for(int j=1;j<=tChars.length;j++){
				if(sChars[i-1]!=tChars[j-1])
					dp[i][j]=dp[i-1][j];
				else
					dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
			}
		}
		return dp[sChars.length][tChars.length];
    }
}
